查看原文
其他

据说这道题90%的人都搞错了

王中阳 王中阳
2024-08-30

题目如下

package main

import (
 "fmt"
)
func main() {
 slice1 := make([]int06)
 slice2 := append(slice1, 1,2,3,4,5,6,7,8,9,10,11,12,13)
 fmt.Println("slice1:", slice1)
 fmt.Println("slice2", slice2, len(slice2), cap(slice2))
}

大家猜一下这题输出的 cap(slice2) 是多少?

~不

~要

~偷

~看

~答

~案

~:)

公布答案

slice1: []
slice2 [1 2 3 4 5 6 7 8 9 10 11 12 13] 13 14

解答

这是一个很常见的关于切片扩容的问题,相信大家也遇到过,首先我跟你们说一下切片的扩容机制:

  1. 当新切片需要的容量cap大于两倍扩容的容量,则直接按照新切片需要的容量扩容;
  2. 当原 slice 容量 < 1024 的时候,新 slice 容量变成原来的 2 倍;
  3. 当原 slice 容量 > 1024,进入一个循环,每次容量变成原来的1.25倍,直到大于期望容量。

很明显这个地方是属于第一种情况,我也给重点标记出来了。

因为slice2是在slice1的基础上进行append,所以可以认为原容量为6(定义slice1的时候设置的),然后一共需要存13个元素,就算扩容两倍到12还是不够,所以应该直接扩容到13......

那么问题就来了,这里为什么会输出14呢?

其实这里就是切片在扩容的时候会进行的一个内存对齐机制,多说无益,直接看源码(在\src\runtime\slice.go):

func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
 oldLen := newLen - num
 if raceenabled {
  callerpc := getcallerpc()
  racereadrangepc(oldPtr, uintptr(oldLen*int(et.Size_)), callerpc, abi.FuncPCABIInternal(growslice))
 }
 if msanenabled {
  msanread(oldPtr, uintptr(oldLen*int(et.Size_)))
 }
 if asanenabled {
  asanread(oldPtr, uintptr(oldLen*int(et.Size_)))
 }

 if newLen < 0 {
  panic(errorString("growslice: len out of range"))
 }

 if et.Size_ == 0 {
  // append should not create a slice with nil pointer but non-zero len.
  // We assume that append doesn't need to preserve oldPtr in this case.
  return slice{unsafe.Pointer(&zerobase), newLen, newLen}
 }

 newcap := nextslicecap(newLen, oldCap)

 var overflow bool
 var lenmem, newlenmem, capmem uintptr
 // Specialize for common values of et.Size.
 // For 1 we don't need any division/multiplication.
 // For goarch.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
 // For powers of 2, use a variable shift.
 noscan := et.PtrBytes == 0
 switch {
 case et.Size_ == 1:
  lenmem = uintptr(oldLen)
  newlenmem = uintptr(newLen)
  capmem = roundupsize(uintptr(newcap), noscan)
  overflow = uintptr(newcap) > maxAlloc
  newcap = int(capmem)
 case et.Size_ == goarch.PtrSize:
  lenmem = uintptr(oldLen) * goarch.PtrSize
  newlenmem = uintptr(newLen) * goarch.PtrSize
  capmem = roundupsize(uintptr(newcap)*goarch.PtrSize, noscan)
  overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
  newcap = int(capmem / goarch.PtrSize)
 case isPowerOfTwo(et.Size_):
  var shift uintptr
  if goarch.PtrSize == 8 {
   // Mask shift for better code generation.
   shift = uintptr(sys.TrailingZeros64(uint64(et.Size_))) & 63
  } else {
   shift = uintptr(sys.TrailingZeros32(uint32(et.Size_))) & 31
  }
  lenmem = uintptr(oldLen) << shift
  newlenmem = uintptr(newLen) << shift
  capmem = roundupsize(uintptr(newcap)<<shift, noscan)
  overflow = uintptr(newcap) > (maxAlloc >> shift)
  newcap = int(capmem >> shift)
  capmem = uintptr(newcap) << shift
 default:
  lenmem = uintptr(oldLen) * et.Size_
  newlenmem = uintptr(newLen) * et.Size_
  capmem, overflow = math.MulUintptr(et.Size_, uintptr(newcap))
  capmem = roundupsize(capmem, noscan)
  newcap = int(capmem / et.Size_)
  capmem = uintptr(newcap) * et.Size_
 }

 // The check of overflow in addition to capmem > maxAlloc is needed
 // to prevent an overflow which can be used to trigger a segfault
 // on 32bit architectures with this example program:
 //
 // type T [1<<27 + 1]int64
 //
 // var d T
 // var s []T
 //
 // func main() {
 //   s = append(s, d, d, d, d)
 //   print(len(s), "\n")
 // }
 if overflow || capmem > maxAlloc {
  panic(errorString("growslice: len out of range"))
 }

 var p unsafe.Pointer
 if et.PtrBytes == 0 {
  p = mallocgc(capmem, nilfalse)
  // The append() that calls growslice is going to overwrite from oldLen to newLen.
  // Only clear the part that will not be overwritten.
  // The reflect_growslice() that calls growslice will manually clear
  // the region not cleared here.
  memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
 } else {
  // Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
  p = mallocgc(capmem, et, true)
  if lenmem > 0 && writeBarrier.enabled {
   // Only shade the pointers in oldPtr since we know the destination slice p
   // only contains nil pointers because it has been cleared during alloc.
   //
   // It's safe to pass a type to this function as an optimization because
   // from and to only ever refer to memory representing whole values of
   // type et. See the comment on bulkBarrierPreWrite.
   bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.Size_+et.PtrBytes, et)
  }
 }
 memmove(p, oldPtr, lenmem)

 return slice{p, newLen, newcap}
}

------------------------------------------

func roundupsize(size uintptr, noscan bool) uintptr {
 if size < _MaxSmallSize {
  if size <= smallSizeMax-8 {
   return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
  } else {
   return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
  }
 }
 if size+_PageSize < size {
  return size
 }
 return alignUp(size, _PageSize)
}

------------------------------------------

// divRoundUp returns ceil(n / a).
func divRoundUp(n, a uintptr) uintptr {
 // a is generally a power of two. This will get inlined and
 // the compiler will optimize the division.
 return (n + a - 1) / a
}

这里简单解释一下:

  1. 首先执行roundupsize函数,64位系统是入参是newcap*ptrsize:13*8=104,32位系统是13×4。
  2. 执行内部的divRoundUp函数得到r1值为7
  3. 取size_to_class8下标为r1的值,得到r2,值为6
  4. 取class_to_size下标为r2的值,得到r3,值为112
  5. r3转uintptr为r4,值一样
  6. 得到112,也就是变量capmem再除以ptrsize,即112/8=14

所以:新容量是14

拓展

这里额外提个问题,欢迎大家在评论区讨论一下:假如系统是32位的,这里的新容量应该是多少?

早日上岸!

我们搞了一个免费的面试真题共享群,互通有无,一起刷题进步。

没准能让你能刷到自己意向公司的最新面试题呢。

感兴趣的朋友们可以加我微信:wangzhongyang1993,备注:面试群。

点击下方文章,看看他们是怎么找到好工作的!

这些朋友赢麻了!

我们又出成绩啦!大厂Offer集锦!遥遥领先!

还有最新鲜的腾讯面经,不要错过哦!

腾讯的面试,强度拉满!

冲进腾讯了!


继续滑动看下一个
王中阳
向上滑动看下一个

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存